package com.wzy.sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: wzy
 * @Date: 2021/09/15/18:12
 * @Description:
 */
public class Test1 {
    public static void main(String[] args) {
        int[] arr = {1, 4, 6, 8, 1, 2, 3, 4};
        // 快排
//        quickSort(arr, 0, arr.length-1);
        heapSort(arr);
        System.out.println(Arrays.toString(arr));

    }

    /**
     * 堆排序
     *
     * @param arr
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) { // O(N)
            heapInsert(arr, i);//O(logn)
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    /**
     * 构建大根堆 依次向根节点比较 向上移动
     *
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 某个数在index位置 是否需要向下移动
     *
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1; // 左孩子的下标
        while (left < heapSize) { // 下方有孩子的时候
            int large = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //父和较大孩子之间 谁的值大，把下标给large
            large = arr[large] > arr[index] ? large : index;
            if (large == index) {
                break;
            }
            swap(arr, large, index);
            index = large;
            left = 2 * index + 1;
        }
    }

    /**
     * 快排
     *
     * @param arr
     * @param L
     * @param R
     */
    public static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
            swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
            int[] p = partition(arr, L, R);
            quickSort(arr, L, p[0] - 1);// <
            quickSort(arr, p[1] + 1, R);// >
        }
    }

    public static int[] partition(int[] arr, int L, int R) {
        int less = L - 1;
        int more = R;
        while (L < more) {
            if (arr[L] < arr[R]) {
                swap(arr, ++less, L++);
            } else if (arr[L] > arr[R]) {
                swap(arr, --more, L);
            } else {
                L++;
            }
        }
        swap(arr, more, R);//相等的在中间 左边是小于的数，右边是大于的数
        // 返回一个长度为2的数组 分别是左边第一个等于该数的下标和右边第一个等于该数的下标            return new int[]{less+1,more};
        return new int[]{less + 1, more};
    }


    /**
     * 归并排序
     */
    public static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }

    public static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        // 该区间有序
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];

        }
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 选择排序
     *
     * @param arr
     */
    public static void xvanze(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                // 因为交换采用位运算 若两个数为指向同一个引用 变成0
                swap(arr, minIndex, i);
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void maopao(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 交互当采用该方式的时候，在数组中下标一样的时间 交换后为0
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swap1(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
